|
|
Practical Efficiency of Containers
Halámka, Jan ; Letko, Zdeněk (referee) ; Holík, Lukáš (advisor)
This thesis is about theorethical and practical comparrison of following data containers: vector, deque, list, hash table, avl-tree, rb-tree, splay-tree, sg-tree, treap, B-tree, binomial heap, fibonacci heap, rope and skiplist while implementing sets. Asymptotic, amortized and average-case complexity for each of those structures are noted, as well as details about their implementation and description of how are they stored in computer memory. There was also created a set of tests for comparrison purposes, its results are also part of this paper.
|
|
|
Fibonacci heaps - their variations and alternative data structures
Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
|
|
|
Fibonacci heaps - their variations and alternative data structures
Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
|
|
|
Practical Efficiency of Containers
Halámka, Jan ; Letko, Zdeněk (referee) ; Holík, Lukáš (advisor)
This thesis is about theorethical and practical comparrison of following data containers: vector, deque, list, hash table, avl-tree, rb-tree, splay-tree, sg-tree, treap, B-tree, binomial heap, fibonacci heap, rope and skiplist while implementing sets. Asymptotic, amortized and average-case complexity for each of those structures are noted, as well as details about their implementation and description of how are they stored in computer memory. There was also created a set of tests for comparrison purposes, its results are also part of this paper.
|
guest ::
